package com.my.algorithmlearning.leetcode;

/**
 * @ClassName Medium_215_FindKthLargest
 * @Description 优秀题解：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/1507044/by-flix-amc8/
 * @Author wanghaiwei
 * @Date 2023/6/16 14:02
 */
public class Medium_215_FindKthLargest {

    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, k);
    }

    private int quickSort(int[] nums, int begin, int end, int k) {
        if (begin >= end) {
            return nums[begin];
        }
        int left = begin;
        int right = end;
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] < pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] >= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        if (left == (k - 1)) {
            return nums[left];
        } else if (left < (k - 1)) {
            //left + 1，因为left已经是pivot了，就是说已经"归位"了，如果不+1，会死循环，因为进入下一个递归中去求解一个已经归位的pivot，就会死循环
            return quickSort(nums, left + 1, end, k);
        } else {
            //left - 1的原理和上面一样
            return quickSort(nums, begin, left - 1, k);
        }
    }

    public static void main(String[] args) {
        Medium_215_FindKthLargest findKthLargest = new Medium_215_FindKthLargest();

        int[] input = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest.findKthLargest(input, 2));

        input = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(findKthLargest.findKthLargest(input, 4));
    }
}
